// 视频链接 https://www.bilibili.com/video/BV1Wp4y1X79x?spm_id_from=333.999.0.0
let graph = [
  {
    vertex: 0,
    edges: [
      {
        adjVex: 1,
        weight: 6,
      },
      {
        adjVex: 2,
        weight: 4,
      },
      {
        adjVex: 3,
        weight: 5,
      },
    ],
  },
  {
    vertex: 1,
    edges: [
      {
        adjVex: 4,
        weight: 1,
      },
    ],
  },
  {
    vertex: 2,
    edges: [
      {
        adjVex: 4,
        weight: 1,
      },
    ],
  },
  {
    vertex: 3,
    edges: [
      {
        adjVex: 5,
        weight: 2,
      },
    ],
  },
  {
    vertex: 4,
    edges: [
      {
        adjVex: 6,
        weight: 9,
      },
      {
        adjVex: 7,
        weight: 7,
      },
    ],
  },
  {
    vertex: 5,
    edges: [
      {
        adjVex: 7,
        weight: 4,
      },
    ],
  },
  {
    vertex: 6,
    edges: [
      {
        adjVex: 8,
        weight: 2,
      },
    ],
  },
  {
    vertex: 7,
    edges: [
      {
        adjVex: 8,
        weight: 2,
      },
    ],
  },
  {
    vertex: 8,
    edges: [],
  },
];

function topo(g) {
  // 初始化入度，全为零
  g.forEach((e) => {
    e.inDegree = 0;
    e.contraryAdjv = [];
  });

  g.forEach((endV) => {
    g.forEach((startV) => {
      startV.edges.forEach((e) => {
        if (e.adjVex == endV.vertex) {
          endV.inDegree++;
          endV.contraryAdjv.push({
            vertex: startV.vertex,
            weight: e. weight
          })
        }   // 同时把逆邻接点求出
      });
    });
  });

  // 初始化栈，将入度为零的顶点压栈，即找到哪些顶点是没有前驱的
  // 删除顶点 -> 元素出栈， 删除该元素对应的弧 -> 邻接点的入度减一 （判断入度是否为零，如果为零，压栈 ）
  let stack = g.filter((e) => e.inDegree == 0);
  let res = [];
  // edges为空是否需要特殊处理
  while (stack.length) {
    let t = stack.pop();
    // console.log(t.vertex);
    res.push(t.vertex);
    t.edges.forEach((e) => {
      let v = g[e.adjVex];
      v.inDegree--;
      if (v.inDegree == 0) {
        stack.push(v);
      }
    });
  }

  return res;
}

let res = topo(graph); // 求得拓扑序列